khash.h File Reference

• Hash for mruby

More...

#include <string.h>
#include <mruby.h>
#include "common.h"

Include dependency graph for khash.h:

Go to the source code of this file.

Macros
#define	KHASH_INITIAL_SIZE   32
#define	KHASH_MIN_SIZE   8
#define	KHASH_SMALL_LIMIT   4
#define	KH_UPPER_BOUND(x)
#define	__ac_isempty(ed_flag, i)
#define	__ac_isdel(ed_flag, i)
#define	__ac_iseither(ed_flag, i)
#define	khash_power2(v)
#define	khash_mask(h)
#define	khash_upper_bound(h)
#define	KHASH_DECLARE(name, khkey_t, khval_t, kh_is_map)
#define	KHASH_DEFINE(name, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal)
#define	khash_t(name)
#define	kh_init_size(name, mrb, size)
#define	kh_init(name, mrb)
#define	kh_destroy(name, mrb, h)
#define	kh_clear(name, mrb, h)
#define	kh_resize(name, mrb, h, s)
#define	kh_put(name, mrb, h, k)
#define	kh_put2(name, mrb, h, k, r)
#define	kh_get(name, mrb, h, k)
#define	kh_del(name, mrb, h, k)
#define	kh_copy(name, mrb, h)
#define	kh_init_data(name, mrb, h, size)
#define	kh_destroy_data(name, mrb, h)
#define	kh_replace(name, mrb, dst, src)
#define	kh_exist(name, h, x)
#define	kh_key(name, h, x)
#define	kh_val(name, h, x)
#define	kh_value(name, h, x)
#define	kh_begin(h)
#define	kh_end(h)
#define	kh_is_end(h, i)
#define	kh_size(h)
#define	kh_n_buckets(h)
#define	kh_int_hash_func(mrb, key)
#define	kh_int_hash_equal(mrb, a, b)
#define	kh_int64_hash_func(mrb, key)
#define	kh_int64_hash_equal(mrb, a, b)
#define	kh_str_hash_func(mrb, key)
#define	kh_str_hash_equal(mrb, a, b)
#define	KHASH_FOREACH(name, kh, k)
	Macro for iterating over all elements in a khash.

Typedefs
typedef uint32_t	khint_t
	khash definitions used in mruby's hash table.
typedef khint_t	khiter_t
typedef const char *	kh_cstr_t

Functions
static khint_t	__ac_X31_hash_string (const char *s)

Variables
static const uint8_t	__m_empty [] = {0x02, 0x08, 0x20, 0x80}
static const uint8_t	__m_del [] = {0x01, 0x04, 0x10, 0x40}
static const uint8_t	__m_either [] = {0x03, 0x0c, 0x30, 0xc0}

Detailed Description

• Hash for mruby

See Copyright Notice in mruby.h

Macro Definition Documentation

__ac_isdel

#define __ac_isdel	(		ed_flag,
			i )

Value:

(ed_flag[(i)/4]&__m_del[(i)%4])

__ac_iseither

#define __ac_iseither	(		ed_flag,
			i )

Value:

(ed_flag[(i)/4]&__m_either[(i)%4])

__ac_isempty

#define __ac_isempty	(		ed_flag,
			i )

Value:

(ed_flag[(i)/4]&__m_empty[(i)%4])

kh_begin

#define kh_begin

(

h

)

Value:

(khint_t)(0)

kh_clear

#define kh_clear	(		name,
			mrb,
			h )

Value:

kh_clear_##name(mrb, h)

kh_copy

#define kh_copy	(		name,
			mrb,
			h )

Value:

kh_copy_##name(mrb, h)

kh_del

#define kh_del	(		name,
			mrb,
			h,
			k )

Value:

kh_del_##name(mrb, h, k)

kh_destroy

#define kh_destroy	(		name,
			mrb,
			h )

Value:

kh_destroy_##name(mrb, h)

kh_destroy_data

#define kh_destroy_data	(		name,
			mrb,
			h )

Value:

kh_destroy_data_##name(mrb, h)

kh_end

#define kh_end

(

h

)

Value:

((h)->n_buckets == 0 ? (h)->size : (h)->n_buckets)

kh_exist

#define kh_exist	(		name,
			h,
			x )

Value:

((h)->n_buckets == 0 ? ((x) < (h)->size) : (!__ac_iseither(kh_flags_##name(h), (x))))

kh_get

#define kh_get	(		name,
			mrb,
			h,
			k )

Value:

kh_get_##name(mrb, h, k)

kh_init

#define kh_init	(		name,
			mrb )

Value:

kh_init_##name(mrb)

kh_init_data

#define kh_init_data	(		name,
			mrb,
			h,
			size )

Value:

kh_init_data_##name(mrb, h, size)

kh_init_size

#define kh_init_size	(		name,
			mrb,
			size )

Value:

kh_init_##name##_size(mrb,size)

kh_int64_hash_equal

#define kh_int64_hash_equal	(		mrb,
			a,
			b )

Value:

(a == b)

kh_int64_hash_func

#define kh_int64_hash_func	(		mrb,
			key )

Value:

(khint_t)((key)>>33^(key)^(key)<<11)

kh_int_hash_equal

#define kh_int_hash_equal	(		mrb,
			a,
			b )

Value:

(a == b)

kh_int_hash_func

#define kh_int_hash_func	(		mrb,
			key )

Value:

mrb_int_hash_func(mrb,key)

kh_is_end

#define kh_is_end	(		h,
			i )

Value:

((i) >= kh_end(h))

kh_key

#define kh_key	(		name,
			h,
			x )

Value:

(kh_keys_##name(h)[x])

kh_n_buckets

#define kh_n_buckets

(

h

)

Value:

((h)->n_buckets)

kh_put

#define kh_put	(		name,
			mrb,
			h,
			k )

Value:

kh_put_##name(mrb, h, k, NULL)

kh_put2

#define kh_put2	(		name,
			mrb,
			h,
			k,
			r )

Value:

kh_put_##name(mrb, h, k, r)

kh_replace

#define kh_replace	(		name,
			mrb,
			dst,
			src )

Value:

kh_replace_##name(mrb, dst, src)

kh_resize

#define kh_resize	(		name,
			mrb,
			h,
			s )

Value:

kh_resize_##name(mrb, h, s)

kh_size

#define kh_size

(

h

)

Value:

((h)->size)

kh_str_hash_equal

#define kh_str_hash_equal	(		mrb,
			a,
			b )

Value:

(strcmp(a, b) == 0)

kh_str_hash_func

#define kh_str_hash_func	(		mrb,
			key )

Value:

__ac_X31_hash_string(key)

KH_UPPER_BOUND

#define KH_UPPER_BOUND

(

x

)

Value:

((x) - ((x)>>3))   /* 87.5% load factor */

kh_val

#define kh_val	(		name,
			h,
			x )

Value:

(kh_vals_##name(h)[x])

kh_value

#define kh_value	(		name,
			h,
			x )

Value:

(kh_vals_##name(h)[x])

KHASH_DECLARE

#define KHASH_DECLARE	(		name,
			khkey_t,
			khval_t,
			kh_is_map )

Value:

typedef struct kh_##name {                                            \
  void *data;          /* Single allocation: [keys][vals][flags] */   \
  khint_t n_buckets;   /* Number of buckets (power of 2) */           \
  khint_t size;        /* Number of elements */                       \
} kh_##name##_t;                                                      \
/* Address calculation functions for optimized memory layout */       \
static inline khkey_t* kh_keys_##name(const kh_##name##_t *h) {       \
  return (khkey_t*)(h)->data;                                         \
}                                                                     \
static inline khval_t* kh_vals_##name(const kh_##name##_t *h) {       \
  return kh_is_map ?                                                  \
    (khval_t*)((uint8_t*)(h)->data + sizeof(khkey_t) * (h)->n_buckets) : NULL; \
}                                                                     \
static inline uint8_t* kh_flags_##name(const kh_##name##_t *h) {      \
  return (uint8_t*)(h)->data + sizeof(khkey_t) * (h)->n_buckets +     \
         (kh_is_map ? sizeof(khval_t) * (h)->n_buckets : 0);          \
}                                                                     \
kh_##name##_t *kh_init_##name##_size(mrb_state *mrb, khint_t size);   \
kh_##name##_t *kh_init_##name(mrb_state *mrb);                        \
void kh_destroy_##name(mrb_state *mrb, kh_##name##_t *h);             \
void kh_clear_##name(mrb_state *mrb, kh_##name##_t *h);               \
khint_t kh_get_##name(mrb_state *mrb, kh_##name##_t *h, khkey_t key);           \
khint_t kh_put_##name(mrb_state *mrb, kh_##name##_t *h, khkey_t key, int *ret); \
void kh_resize_##name(mrb_state *mrb, kh_##name##_t *h, khint_t new_n_buckets); \
void kh_del_##name(mrb_state *mrb, kh_##name##_t *h, khint_t x);                \
kh_##name##_t *kh_copy_##name(mrb_state *mrb, kh_##name##_t *h);                \
void kh_init_data_##name(mrb_state *mrb, kh_##name##_t *h, khint_t size);       \
void kh_destroy_data_##name(mrb_state *mrb, kh_##name##_t *h);                  \
void kh_replace_##name(mrb_state *mrb, kh_##name##_t *dst, const kh_##name##_t *src);

KHASH_FOREACH

#define KHASH_FOREACH	(		name,
			kh,
			k )

Value:

if (kh) \
  for (khiter_t k = kh_begin(kh); !kh_is_end(kh, k); k++) \
    if (kh_exist(name, kh, k))

Macro for iterating over all elements in a khash.

Usage: KHASH_FOREACH(typename, kh, k) { // k is the khiter_t iterator // Access the key with kh_key(typename, kh, k) // Access the value with kh_val(typename, kh, k) if applicable // Your code here }

Parameters

name	The hash type name
kh	The khash to iterate over
k	The name to use for the khiter_t iterator variable

khash_mask

#define khash_mask

(

h

)

Value:

((h)->n_buckets-1)

khash_power2

#define khash_power2

(

v

)

Value:

  do { \
  v--;\
  v |= v >> 1;\
  v |= v >> 2;\
  v |= v >> 4;\
  v |= v >> 8;\
  v |= v >> 16;\
  v++;\
} while (0)

khash_t

#define khash_t

(

name

)

Value:

kh_##name##_t

khash_upper_bound

#define khash_upper_bound

(

h

)

Value:

(KH_UPPER_BOUND((h)->n_buckets))